class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(1 == len) {
            return nums[0];
        }
        int[] arr = new int[len];
        arr[0] = nums[0];
        //偷这件房屋,不偷这件房屋(那么走到第二件屋子所能偷到最大的是前k间房屋的最高金额)
        arr[1] = Math.max(nums[0],nums[1]);
        for(int i = 2;i<len;i++) {
            //偷这件房屋(最大值是这间房屋加上前k-2间房屋的最高金额),不偷这件房屋(那么走到第二件屋子所能偷到最大的是前k间房屋的最高金额)
            arr[i] = Math.max(arr[i-2]+nums[i],arr[i-1]);
        }
        return arr[len-1];
    }
    public int rob1(int[] nums) {
        int len = nums.length;
        if(1 == len) {
            return nums[0];
        }
        int[] arr = new int[len];
        arr[0] = nums[0];
        arr[1] = nums[1];
        int max = Math.max(arr[0],arr[1]);
        for(int i = 2;i<len;i++) {
            for(int j = i-2;j>=0;j--) {
                arr[i] = Math.max(nums[i] + arr[j],arr[i]);
            }
            max = Math.max(arr[i],max);
        }
        return max;
    }
}